1. Field of the Invention
The present invention relates to a secret sharing apparatus, method, and program using a (k,n)-threshold scheme, and for example, to a secret sharing apparatus, method, and program enabling implementation of the (k,n)-threshold scheme that can be performed at a high speed without using polynomial interpolation.
2. Description of the Related Art
In general, pre-making a copy of secret information such as an enciphering key is effective for providing for a possible situation in which the secret information is lost. However, making a copy of secret information disadvantageously increases the risk of theft. As a technique for solving this problem, Shamir has proposed a secret sharing scheme called a (k,n)-threshold scheme (see, for example, A. Shamir; “How to Share a secret”, Communications of the ACM, 22, 11, pp. 612-613 (1979)).
The (k,n)-threshold scheme divides secret information into n pieces of sharing information so that the original information can be restored by collecting any k of the n pieces of sharing information but so that no information on the original secret information can be obtained from k−1 pieces of sharing information. That is, the (k,n)-threshold scheme has the property of restoring secret information using a threshold k as a boundary (1<k<n).
Thus, according to the (k,n)-threshold scheme, even if at most k−1 pieces of sharing information are leaked, the original secret is secure. This makes it possible to achieve management such that even if at most n−k pieces of sharing information are lost, the original information can be restored.
However, the Shamir (k,n)-threshold scheme executes processes of sharing and restoring secret information using polynomial interpolation, which requires a large amount of calculation. Thus, the Shamir (k,n)-threshold scheme disadvantageously requires high-speed calculation in order to allow a large amount of secret data to be shared.
On the other hand, a scheme of Fujii et al. and a scheme of Kurihana et al. are known as (k,n)-threshold schemes solving these disadvantages to enable a sharp reduction in calculation amount (see, for example, Yoshihiro Fujii, Minako Tada, Norikazu Hosaka, Koya Tochikubo, and Takehisa Kato: A Fast (2,n)-Threshold Scheme and Its Application”, SCC2005 collection of preliminary papers, (2005), and Jun Kurihara, Shinsaku Kiyomoto, Kazuhide Fukushima, and Toshiaki Tanaka: “A (3,n)-Threshold Secret Sharing Scheme using XOR Operations”, SCIS2007 collection of preliminary papers, (2007)). The scheme of Fujii et al. and the scheme of Kurihana et al. can be performed at a high speed because the schemes execute the processes of sharing and restoring secret information using only exclusive OR operations.
However, the scheme of Fujii et al. and the scheme of Kurihana et al. disadvantageously limit the threshold k to 2 or 3.
As described above, the Shamir (k,n)-threshold scheme uses polynomial interpolation, disadvantageously requiring high-speed calculation. On the other hand, the scheme of Fujii et al. and the scheme of Kurihana et al. disadvantageously limit the threshold k to 2 or 3.